package com.huangpeng.algorithm.dataStructure;

/**
 * @Author hp
 * @Title 二分查找-最简单实现
 * @Package
 * @Date 2022/1/28 10:58
 * @Description
 * @Version 1.0
 */
public class DichotomySearch{
    /**
     * 原始，连续数组有序，无重复数字
     * @param a
     * @param n
     * @param value
     * @return
     */
    public static int bsearch(int[] a,int n,int value){
        if(a == null){
            return -1;
        }
        int low = 0;
        int high = n - 1;
        while(low <= high){
            int mid = low + ((high - low) >> 1);
            if(a[mid] == value){
                System.out.println("原始####### " + mid);
                return mid;
            }else if(a[mid] < value){
                low = mid + 1;
            }else{
                high = mid - 1;
            }
        }

        return -1;
    }

    /**
     * 变体一，连续数组有序，有重复数字，查找第一个值等于给定值的元素
     * @param a
     * @param n
     * @param value
     * @return
     */
    public static int variantSearch1(int[] a,int n,int value){
        if(a == null){
            return -1;
        }
        int low = 0;
        int high = n - 1;
        while(low <= high){
            int mid = low + ((high - low) >> 1);
            if(a[mid] > value){
                high = mid - 1;
            }else if(a[mid] < value){
                low = mid + 1;
            }else{
                if((mid == 0) || a[mid - 1] != value){
                    System.out.println("变体一####### " + mid);
                    return mid;
                }else{
                    high = mid - 1;
                }
            }
        }

        return -1;
    }

    /**
     * 变体二，连续数组有序，有重复数字，查找最后一个值等于给定值的元素
     * @param a
     * @param n
     * @param value
     * @return
     */
    public static int variantSearch2(int[] a,int n,int value){
        if(a == null){
            return -1;
        }
        int low = 0;
        int high = n - 1;
        while(low <= high){
            int mid = low + ((high - low) >> 1);
            if(a[mid] > value){
                high = mid - 1;
            }else if(a[mid] < value){
                low = mid + 1;
            }else{
                if((mid == n - 1) || a[mid + 1] != value){
                    System.out.println("变体二####### " + mid);
                    return mid;
                }else{
                    low = mid + 1;
                }
            }
        }

        return -1;
    }

    /**
     * 变体三，连续数组有序，无重复数字，查找第一个大于等于给定值的元素
     * @param a
     * @param n
     * @param value
     * @return
     */
    public static int variantSearch3(int[] a,int n,int value){
        if(a == null){
            return -1;
        }
        int low = 0;
        int high = n - 1;
        while(low <= high){
            int mid = low + ((high - low) >> 1);
            if(a[mid] >= value){
                if((mid == 0) || a[mid - 1] < value){
                    System.out.println("变体三####### " + mid);
                    return mid;
                }else{
                    high = mid - 1;
                }
            }else{
                low = mid + 1;
            }
        }

        return -1;
    }

    /**
     * 变体四，连续数组有序，无重复数字，查找最后一个小于等于给定值的元素
     * @param a
     * @param n
     * @param value
     * @return
     */
    public static int variantSearch4(int[] a,int n,int value){
        if(a == null){
            return -1;
        }
        int low = 0;
        int high = n - 1;
        while(low <= high){
            int mid = low + ((high - low) >> 1);
            if(a[mid] > value){
                high = mid - 1;
            }else{
                if((mid == n - 1) || a[mid + 1] > value){
                    System.out.println("变体三####### " + mid);
                    return mid;
                }else{
                    low = mid + 1;
                }
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        int[] a = {1,2,3,4,5,6};
        int n = 6;
        DichotomySearch.bsearch(a,n,5);

        int[] a1 = {1,2,3,3,3,4,4,5,6};
        int n1 = 9;
        DichotomySearch.variantSearch1(a1,n1,4);

        int[] a2 = {1,2,3,3,3,4,4,5,6};
        int n2 = 9;
        DichotomySearch.variantSearch2(a2,n2,3);

        int[] a3 = {1,3,5,7,9,11};
        int n3 = 6;
        DichotomySearch.variantSearch3(a3,n3,8);

        int[] a4 = {1,3,5,7,9,11};
        int n4 = 6;
        DichotomySearch.variantSearch4(a4,n4,6);
    }
}
